{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "source": [ "# Interactive Gradient-Descent in Python\n", "\n", "## Try me\n", "[![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/NLP/tutorials/Interactive%20Gradient%20Descent.ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FNLP%2Ftutorials%2FInteractive%20Gradient%20Descent.ipynb)\n", "\n", "## Introduction\n", "Gradient-Descent (GD) methods are in the backbone of many machine learning methods. in this tutorial, we will use a practical example to illustrate how the simplest algorithm in the family (Simple Gradient Descent) works.\n", "\n", "\n", "## Import libraries\n", "Before we dive into GD methods, let's import the libraries that we will use in this tutorial:" ], "metadata": { "id": "aa0c08nGdcTc" } }, { "cell_type": "code", "source": [ "import numpy as np\n", "import pandas as pd\n", "from matplotlib import pyplot as plt\n" ], "metadata": { "id": "Qlc0gVtyU999" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "## Problem definition\n", "Gradient-Descent methods allow us to find the maximum or minimum of a function that depends on an array of variables:\n", "\n", "$$x = [x_1, x_2, ..., x_n]$$\n", "\n", "For minimization, we want to find the minimum value of a function of x: \n", "\n", "$$\\min z = f(x)$$\n", "\n", "And similarly, for maximization, we want to find the maximum value of the function in x:\n", "\n", "$$\\max z = f(x)$$\n", "\n", "### Tutorial Example\n", "In this tutorial, as an example, let us find the maximum of the following function:\n", "\n", "$$\\max z = f(x) = (8-x_1)*x_1 + (16-x_2)*x_2$$\n", "\n", "Note that it is a quadratic expression, probably the simplest form of non-linear function. We have chosen this function because it is relatively easy to analyze, so we will use it to get insights on Gradient descent methods.\n", "\n", "#### Implementing the function in Python\n", "The following Python function returns this value, given that you pass $x$ as a list or array:" ], "metadata": { "id": "5doU7dH6ddJT" } }, { "cell_type": "code", "source": [ "def my_func(x):\n", " # This is the function to optimize. \n", " # x is an array containing the dependent variables to optimize (x = [x_1, x_2, ..., x_n])\n", " # By default this is the function used in the example, \n", " # but you can change it if you want to analyze other examples\n", " return (8-x[0])*x[0] + (16-x[1])*x[1]\n" ], "metadata": { "id": "8aixZJOwVCNV" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "Now, let's plot it to get a general idea of how the function looks like. The following script represents a contour plot of the function:" ], "metadata": { "id": "tZaLo34WkZ8l" } }, { "cell_type": "code", "source": [ "x_1 = np.arange(-20, 20, 0.01) # The horizontal axis of the contour plot, it will represent x_1\n", "x_2 = np.arange(-30, 30, 0.01) # The vertical axis of the contour plot, it will represent x_1\n", "xx, yy = np.meshgrid(x_1, x_2, sparse=True) # This is a 2D grid of points where the function wil be evaluated\n", "z = my_func([xx, yy]) # We then calculate function z \n", "h = plt.contourf(x_1,x_2,z,levels=20)" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 265 }, "id": "9cBK__uUkZOm", "outputId": "3ceeec4c-80ef-411b-993b-78cff3e9aadd" }, "execution_count": null, "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXkAAAD4CAYAAAAJmJb0AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAAsTAAALEwEAmpwYAAAgW0lEQVR4nO3df6xkZ3nY8e+zd9emu3bAC3Qx9pYlikE1VdWqyK3UVm0EbQxKsiFpIlOpMYmlFVIiFKlVsGu1iYQsuUKlitq06VZFOBGJg5RSWykV2JZaFAmXGEqDHaCswZbtGls2v3dh1/fu2z9m3vXZc8+ZOTPnfc/7PO95vtJq7525O/PuzDmf8+y5c2clhIDneZ5XZwdKL8DzPM/LlyPveZ5XcY6853lexTnynud5FefIe57nVdzB0gtotnPVkXDw6NHN/tCBhK8OSnlbrXZ2pnkV086Bi5Pcz7oOHdgrvQR1XaHkMblwcaf0EtT1kpLHZO/idnP3D848+0II4bVd16lC/uDRo1z3z35t0NfuHUm3wxw8spvstpodOfLDLLfb7ujhc5Pcz6qOHf5+6SVk7fjhb5VegqqeOndN6SVk77lzV5VeAt88d3jQ133xpz/wZN91qpBfV0rYIQ/uU8BeGvWaQHe8t2uTx83qAaG9nZdAv7mvDwW/nQnktU/ttcNuFXUHXEfrngcrB4HS6G8Lvmrk5457Kdgtoe6Q22/Vc6j5AFAS/U3AV4m8ZtxrhN0C6o75PLN0ACiF/jozdCF/ICQD3hLuU8OuGXXH3Bta17aiCf7Sp3diupAfmbVTMlPirhF2B91LnWb4m/vglOBXgbxP7d1pgt1B90qlEf4pp3zTyFvBfW6wO+iLjl/5YuklDOqp868uvYTJ0wZ/zinfJPKO+8s56vmzgvW2bfv3q+3g0N6OS6GfGnxTyFvAfaqpvSTuNaFeO+A5G/LYWT4QaEA/BfhmkE8JvFXcHfbNc8TLtu7xt3QQKI3+tuCrR37uuJeC3RrqjrnN+p43C/g395FS4A/BXi3ymnF32MvlmM8ja/iXmvKHWKEOecd9urSj7qB77bq2CY3wl5zy2+lCPtH7uVvC3WFf5KB726Yd/tLg60J+ZI57dxphd9S9nLW3Ly3olwC/CuQd9+404e6oeyXTOO1PBb555FMCnwv3OcLuqL/ciSteKL2E3p648JrSSyhWcxvVAn4O7M0i77i/nAbY54K6ZrC3adO/T60HBS2nd3JM9+aQd9xfrjTutcFeG+A5GvIY1XAg0DDlpwLfFPLagZ8Cd4d9XA55/lY9xhYPABqm/DGnc0wg77iXw90q6o65zvqeF0v4l5zyt8FePfKpgHfcN7xfQ7g76Pbreg4twF8K/E1O5ahFXvP0nht3h70/B30+WYNfA/hdqUR+rtN7Cdy1w+6oe83a24NW9ON+VfqlmaAM+Z2doBb4mnDXDLuj7m2SdvQ1vEpHFfIpctxX3J9C3B11L2Wa0S813VeFvBXg5467w+5NlUb0p57uq0DeCu4wHfCaYHfUPS01t0VN4OfE3jzyKYF33NPlsO/vxEEdz80Tu+W/GaghTeDnxN4s8lam9znhPkfYtcC9SZuueQ4HBS3g58B+NPIichz4XeAYEIDTIYTfEpGjwB8CJ4AngF8IISQRz8L07rjXkUXEU7fqMajxAKAB/JTYp5jkd4F/GkL4vIhcDXxORB4A3gM8FEK4W0RuB24H3j/2zhz45X0Uxr022B3z7ar9ABC3c8vYj0Y+hPAs8Ozy4++JyJeA64CTwN9fftk9wP9gJPLagXfc9eeYT1fXY20V/tLT/Rjsk56TF5ETwF8H/hdwbHkAAPgGi9M5W6Udd8gPfEncLcPuqOuqBvhLTvfbYJ8MeRG5Cvgj4NdCCN8VkUvXhRCCiHT+L90icgo4BXDota/cd7124Gue3q3h7qDbrP28WUHfCvZJkBeRQyyA/2gI4b8sL35ORK4NITwrItcCz3f92RDCaeA0wOEbXn/ZgWDuwDvu63PY68sa+iVP5Ry/8sW10Kd4dY0A/xn4UgjhQ42r7gduBe5e/n7fJrerGXjHvVyO+vxqPudWwJ8S+3VepJjk/zbwT4AvisgXlpf9cxa4f0xEbgOeBH5h6A2mAt6n92Fpx91h92JWwC/9qpxmKV5d8yeA9Fz9tk1vb67AO+6X57B767IAvgbsVf3E686Bi0lux4FfnVbcHXZv27SDf+KKF4pBrwr5FFk6/+64O+xe+rSCX2qqrwp5B747x92ba3E7mzP21SDvwHenDXjH3SuRxul+qlM4VSBvBfi54u6we5rSNN1PMdWbR96B358W4B33Yb0h01745G6e260lbdjngt408g785TnuesoFd641zPmAoAX7XFO9gk1xuxz4y9MA/Bxx14B5ivr+HnPCXxP2KaGvZBMdlwOfYA0zAL4W0DdpjvhrwD4l9CY325RTvAM/8v4rxX2OoG9S+/GpEf0TB18sDj2MP31jblN24Bc57ulz2LevVvRrmOpNbdYO/CIHPk2Oer6aj20N4GuY6reF3jfzhNUOfA24O+zTVwv4paf6baE/kGEtWdI+xTvwunvDQQdeQ/F5sPxclNwXtjHABPIOvAO/TTWAUnOWnxtL0JtAfu458JtlGY85ZvX5OnHwxWL7xyYmqEd+7lN8KeBLbsDbZhULb5HV50879KqRnzvwpXLcvZJZfD41Q68a+blXYoq3BLxFDLzhWXt+tUKvFvm5T/EO/Oos7fzeuCxhr3EfUou85moE3kqWdngvbVaed23QV498zv/hqaa0bZhdWdnJvXxZOchr2p9UIp/6bYRTVuMUr2mD7MrKju1Nl28Pw1OJfKqsTfEO/P58Z/b60r5taNm31CE/5yneuzztO7FXPu3biAbo1SGfKp/iB9yngg2wL+07r6cn31ZWVy3yqattinfgvZrSvM2U3tdUIX/owF7pJXieZzTN0JcsCfIi8mEReV5EHm1cdlREHhCRry5/vybFfQ3JT9WsuT+f4j1v0kruc6km+Y8AN7cuux14KIRwA/DQ8nPP682B98bm29D+kiAfQvg08M3WxSeBe5Yf3wP8TIr7KlFt5+M9r+a0Ql9qms95Tv5YCOHZ5cffAI51fZGInBKRR0TkkfPf+mHG5ejMT9Us0rpjep71JvnGawghAKHnutMhhLeGEN565TWvmGI5nudVng8NL5cT+edE5FqA5e/PZ7yvS1n7pqvnO6Q3n0r8Szon8vcDty4/vhW4L+N9eZ7neR2legnlHwCfAd4sIk+LyG3A3cA/EJGvAm9ffu4VTOv5eM/z8pXkH8ohhHf3XPW2FLdfMn9ljed5llP1E6+e53mp8u/1LHLkPc/zKs6R9zyvyp7cLb0CHTnya3rq/KtLL8HzPG/rHPkZ9cSuH7A8b2458p7neRVXHfJPnZvsHY29RPm5U28ulfjXdHXIe57n+eDwco584Z648Jpp70/peXnfKT0vT478gPwVNp5nJ60DQ6kBy5H31KR15/Q8y1WJvH/zdXVaT9l43th8UNifKuRfurhTeglFmvq8vOZ8J/W2TfO2U3KwUoW85mo7L695mte8s3o607zNlN7XqkXe2ikbn+YvT/NO6+nKt5XVqUP+uXNXlV5Cbz7NT5vvvN66tG8jGvYxdcinzKf5AfepYCNclfad2CuX9m1Dy75VNfI5yj3NO/T7e3JX/w7tTZtvD8NTibzmUzZeuXzH9qwc8DUNTiqRT1mOUzY+zZfLwg7u5cnKc69tX1KLfMpp3tq5eXDoV2VlmvPSZOn51rgPqUVee7W90iamcSPty9LO722Xpee31L6zbiBUjbz2ab7G0zZgC3pw7GvM2nOqFXhQjjzo/yasQ68nazB4+7P4HGoGHgwgnzKL5+ahLPSOvZe7+HxZfM60Aw9GkJ/7aRso+7YHFqEHu3DMJcvPT8kBaFMLTCCfOod+i/s2Cj3YnhRrq4bnouS+sI0B2ZEXkZtF5CsickZEbt/2drSfm4d5QG8Ze6gDGWvV9JhbAx4yIy8iO8BvA+8AbgTeLSI3bnt72k/bQP3Qg+2pvllN+Girtse29IAzZp/PPcnfBJwJIXwthHABuBc4OeYGHfpFGqCvBXu4HKVaYJqyWh8/Ddv52H09N/LXAU81Pn96edmlROSUiDwiIo+89O1zmZezP+vQa8C+xmpFK1VzeHw0bNsp9u+DCdYxqhDCaeA0wNVvfl0Y8meeO3cVxw5/P9kanjp3DccPfyvZ7V263fOv5viVLya/3XZPXHgNJ654Ifv99N7/cmc4cTD/37VUXZC9ofjeM021It5XLbjHcm+mzwDHG59fv7xsdA795ZWGHuaBfbM+/KziPzfM22nAHdKfis29Of4pcIOIvJEF7rcA/zjVjTv0lxc3Dse+bEOxnOpgMHe816UFd8jzvbasm1kIYVdEfhX4JLADfDiE8FjK+3Do96dhqgfHfl2Ob9lqxz2WfZYIIXwC+ETO+7AEPTCrqR4ce09XmnCH/K+Uq+YnXlP/sFTO97mZ8m2KS7/6pll8OZq2ncybR9q2valeHWf0W0TdWZnoYfrTN6Bjqo/5dO9NkSbUY1MPXlUhD/agh2lO34Bu7MHB99KlEXco8y9rVcjvXUxz9igH9EAVUz3o+cZsOwffG5NW2KHsaVNVyAN889xhjh4e/5OvqaEHn+qnzE/neEPSDDvo+J6YOuRhvtBDmake9GMfc/Q97bCDDtxjKpGHtNAD5k7fwHRTPejHPuandOaXBdRjmnCPqUUe0kEPPtUPrbmRWgIfHP1asoR6rBTuQ16OrRp5cOhLTPUxK9N9zNG3mUXUoezUvsnP2qhHHtJDD7ZO34Bjv01deDj85bOKeswK7jETyMMCekD9VA/1Yw/2wI85/NNlHfN21nCPmUE+pv30DeQ/hQNlsQe7031XfRg5/sOqDfNmGr6ROvZtUMwhD/pP38A0Uz3owR7qAL/ZKrzmdgCoGfJ2NcDezCTyYOP0DcwHe6gb/HaboKf1gDAnuNelAXbI8+aFZpGPWZjqYZpTOKADe5gX+OtyTHWmBXbI+8605pGHtNCD/ake9GAPDr6nJ02wwzRvO14F8pDn9A3km+phWuxBH/jg6Hv50wY7TPt/SlSDfCzHVA/2sQdd033Mp3wvdRpRh2lhb6YK+b09SXI7qad6yHcKB8phD3rBB0ffG5ZW1GOlcI+pQh7g7NlXAHDkyA9H35alqR6mxx50Tvexrp3X4fe0ow7lYW+mDvnY2bOvSAY9pJ/qoU7sQSf4MZ/255UF0GOlYF/3/1GrRR7ST/VgE3tw8PvqQ8Dxt5cl0GMlJ/Z1uMdUIx9LNdVD+lM4kB97KDPdgy3wmzn+erOIeTMLsDczgTzon+qhbuzBLvjNHP9psg55u9Ln2LfBPWYG+Zhjv6jUqZxL99/a6K2iHxuCkh8IFtUGeFelUYdxsDczh3ws9SkcsIk9lJ3uL62hgil/XZviZumgMAe416UBdkiHe8ws8pB2qod6sAc94EO96K/L4dSdFtQhPezNRiEvIj8P/Cbwl4GbQgiPNK67A7gN2APeF0L45Jj7WpU17GE+4IOj7+lIE+qQF/ZmYyf5R4GfBf5j80IRuRG4BXgL8HrgQRF5Uwhhb+T9rcwK9jDddA+6wIfunc3h91KnDXWYDvZmo5APIXwJQGTf2xGcBO4NIZwHvi4iZ4CbgM+svMGLad7WIOX5eqgHe9AHfsynfW9MGkGPlYC9Wa5z8tcBDzc+f3p52b5E5BRwCmDn6KvYPbtY0sEju6MWkHqqh2mwBwcffNr3+tMMeqw07M3WIi8iDwKv67jqzhDCfWMXEEI4DZwGuPLE9SFePlfsoTz4oA996N+5Hf86s4B5s1KwN73oai3yIYS3b3G/zwDHG59fv7xs43bPHhwNPeTFHvKDPxX2Mc1TfrtVGPgBQH/WMI+VnNbXwd4s1+ma+4HfF5EPsfjG6w3AZ7e9sVRTPeTBHuqc7mMWpvy+/ABQPquItyt9CmYT2JuNfQnlu4B/C7wW+G8i8oUQwk+EEB4TkY8Bfw7sAr+S4pU1ObAHW6dyoCz4YBv9ZkPw8QPB6moBvC+rsDcb++qajwMf77nuLuCuMbffV0rswe6pHCgPPtSDflfbIGb5wFA72qsqDXosBezNTP/EqwXsYZrpHnSAD3WjP6Q5Q2kpLahDetibmUY+Zg17mBZ80IU+zA9+r2yaQI/lhL1ZFcjHcmEPtsEHPVN+zOH3cqURdJgO9Xa6kL8o7JzdYe/IuO/RpsYe8k33UBZ80IE+9O+cjr/XlVbMm5WCvZku5JftnN0BSIY92JjuYXrwQd+U387xn3cWMI9pQL2dSuRjqbAHe9M9lAcfdKIfW7Xz+wHAVpYgb1YK9aYN61KNfMwK9lAX+NC9EWuGP7YODT8ITJtVxNuVnNQ3gb2ZCeRjObAHB3/TLE37fW2Cjh8Q+qsF7640nHrZFvZmppCPpcQe8kz3kP90DuzfCDSgDzbh72sMZNoPEDUjvWkaUIc0sDcziXwsYg8+3cdKT/mx2uEfmiOqLy2Yx1Kj3s408s2sTfcwLfhQFn1w+L3p0wY65Ee9nSrkJYHPubAH2+CDPvShfyd0/L1N0oh5bGrU26lCHuDg9w4AsHv1xVG3k/pUDkwHPswX/diqndYPAPNMM+TNSqPeTh3ysYg9pAM/FfaQF3yYfsoH3eg38wNAvVmBvFkp1NuDYV9qkW+mebqHfOfvYyWmfOjeeLXCHxuChB8IymQR8Halp/ShsDczgXwsFfaQ/3QOTIP+VODHLMLfblNs/KDQXw1w91UadNgO9XamkI+lPJUDeU7nQP5TOlBuym9WA/yrSgGZtgNFzThvkwbQIQ3q7Uwi30z7dB+bAnzQgT707zQ14b9JjqqOtGAey4F6O/PIx3JN92AXfNCDfszx96ZIG+axKVBvpwp5uQgHz8LukXG3k3K6h+nAh/mhH1u1U/oBwOtLK+axEqi3U4V87ODZxe+psAcb4MO0Uz50b4Ra4I/5AWC+aUe8WSnQ24NiO5XIxyL24ODDNOiDDfhjQxDwA4HOLAHeruSEvg71dqqRb5Zqugeb4EM59MEW/O02wcQPCOOyDHdfpU+5bIp6OzPIx1JO95AffKgTfejf+K3g39VYpKwfJGpEepNKgw7jUW9nDvlmFsCHaaZ8KI9+rEb8hzZ3JK2kAfNYatTbmUa+WcrTOTAN+DAt+lAOfpg3/t70aYK8WW7U26lCXi7CobPw0gioU0/3kA98mBZ90DPtN1u1M/oBwFuVVshjU4Pe1agViMgHgZ8CLgCPA78UQvj28ro7gNuAPeB9IYRPDr3dQ0uox2AP9sCH6U7txLRN++2G7MR+IKg37Yg3KwV6e1BsN3ZVDwB3hBB2ReRfAXcA7xeRG4FbgLcArwceFJE3hRA2UutQA2nt4IP9KT/Wt7Fqwr+ZHwjsZQnvrkpO6OtQbzdqpSGETzU+fRj4R8uPTwL3hhDOA18XkTPATcBntr0v7eDDtFN+bCr4Qf/Uv6ptUPEDw/Cso92XhtMtm6LeLuXf4JeBP1x+fB0L9GNPLy9LkjXwIQ/6UG7aj1mb+jcpJVzaDhi1orxtGjCH8aB3tfZvJiIPAq/ruOrOEMJ9y6+5E9gFPrrpAkTkFHAK4NDVm//P9rnAB1tTfqz0tB9btdPUcADYNEe1fFogb5YD9XZr/9YhhLevul5E3gP8JPC2EEJYXvwMcLzxZdcvL+u6/dPAaYDDx46Hrq8ZWkrwwf6UH9MCf8wPAF6uNEIemwL0rsa+uuZm4NeBvxdCaP6o3/3A74vIh1h84/UG4LNrb28PDn1/4fxLV8mYpZkBH6ZHH/TBH1v7Zkt+EJh1mhFvVgr0rsY+Yv8OuBJ4QEQAHg4hvDeE8JiIfAz4cxancX5l41fWfP/loV4z+JAffZg3/M2G7uR+MLCXFcCblcS8y4nOrxtzJyGEH1tx3V3AXWNuP6YZfMiPPpSZ9qF/I9aGf7tNwPADQp4sot1X6cl8KOidfzbhOiZJO/iQ99TOpfsoNO3HrOLfVQqMajtQ1AT0JpXGPDYG9X23leyWCpQLfLA15V+6r0LTfrNVO4nFA8DQ5oqixbRAHksJeuftZ731CUsJPkwz5cemnPahDP6wfueq+SDgTZs2yGO5Qe+8z8nvcUVyEa743gLrC1dvD3VO8CEt+jDttA/lT/X05QcBb0haAW9WAvO+VCHfLGIP6cAHR7/3PpVN/V0N3bn9YGAzC3h3VQr0rrMCnV+XdxlpSgU+pJ/yYXr0YRr4wQb+7TbFwg8KebKKdlelJ/OhoHf+2XTLmCbt4EN+9KEs/GAT/75SYVTTwaImoDepNOaxMajvu610NzV9ucAHe+hDefhh/U5i8SAwtLnCaC0tkENazHvvI/9dTFNK8KEO9EEH/M3mfBDwpkkT4s2mAL3zfsvcbXeyF7jiu4sfKrnwI9svrQk+2EMfpocfyuIfG7KD+oFgvmkFvFkpzPtShXyziD2MAx/ST/mQF32YdtqPaca/2SY7uh8Q9GcB7q5KYt41GPalFvlmTfBB35QP06MP08APqzdmbQeAdtsA4geG7bKK9bpKT+abgN6VCeTb5ZrywQ76UBb+mOUDQF+5sSp1EKkV4bGVRrzZWNC7Mol8s5Tgg230oX8jmRp/WL/zWD0IjM2xnT5NkEMezPtShbzsjfqPoZKe1rl0mxnO58N+9CEf/KAL/5gfBLwUaQO83ZSgd6UKeYBD333pss9f+pFDW99WavTbUz7Yhh904h/bZOf1A0J9ace7WSnIu8xopw75dk30x4AP6U/tQL7TO7ES8MPqjVbDAaDdpiD4QWHaLIG9qpJT+RDQu1KPfDPNU/6l282MPpSD/9L9GzsAdJUSnZoPGLXgvEmlT6/A9qB3ZQr5drmmfMiHPkwHP0yLP6zfQawcBDZpjhBaTgPisZSY92Ua+WYpp3zIhz5MBz/owT82x4OAN12aAG82BeZ9qUJe9i6y850fXPp875V/YevbSjnlQ170YVr4QR/+sU12Uj8gzCeteLcriXlfqpBvlwN8yIM+2IcfVm+kpQ8A7Tbd8f2goCMrYPdVGvIuF1alGvlmTfBBH/qQf9qHMvDHLB0AukqBy9wPFNaBHlppyGFzzPsyg3w7i+jDdPDDdPjD+p3CwkFgSHNBrvY0IB5LhXlfZpFvl+rUDuxHH+zBDzrwjw3ZqWo5EHhl0wR4s9yY96UL+b2LyHe+d+nT8Mqrt7qZlFN+LNe0D9PCD6s3thIHgNgmO6cfEOaVVri7KoV5X7qQb5UCfJgGfcgPP+TFH/QeANptutP7QUFXltDuqiTkfTb0pRr5Zk3wQR/6kHfaj0099V9230YOAF2lQmXuBwvrOA9NwzS+KeZ9jdJBRD4AnAQuAs8D7wkh/D8REeC3gHcC55aXf37sYi+774zog41pP1Zq6r9sDQN2Cu0HgiHNBbna04B4LBXmfY1V4IMhhH8BICLvA/4l8F7gHcANy19/E/gPy9+zlRJ9mG7ahzzww+qNZ8oDQGwuBwKvXJrwbpcb875G7ekhhO82Pj0CxEf4JPC7IYQAPCwirxKRa0MIz668wb1dLn7r25c+PXDNq7ZeW270IS/8kA9/0DH9d7XJTuoHhHmkGe52pSBf1eg9WkTuAn4R+A7w48uLrwOeanzZ08vL9iEvIqeAU8tPz3/q3O89eunKc2NX1+iZhLcFrwFeSHqLefJ1ps3XmS4LawQ763xD3xWyGLb7E5EHgdd1XHVnCOG+xtfdAbwihPAbIvLHwN0hhD9ZXvcQ8P4QwiNr7uuREMJbVy5IQb7OtPk602ZhnRbWCHbWuaq1k3wI4e0Db+ujwCeA32AxNx9vXHc9qWdpz/M8b22j/kdhEbmh8elJ4MvLj+8HflEW/S3gO2vPx3ue53nJG3tO/m4ReTOLl1A+yeKVNbCY6N8JnGFxZv2XBt7e6ZHrmSpfZ9p8nWmzsE4LawQ76+xt7Tl5z/M8z26jTtd4nud5unPkPc/zKk4F8iLyQRH5soj8mYh8XERe1bjuDhE5IyJfEZGfKLhMROTnReQxEbkoIm9tXH5CRH4gIl9Y/vodjetcXqfm8WwmIr8pIs80HsN3ll5TTERuXj5eZ0Tk9tLr6UtEnhCRLy4fv5UvV54yEfmwiDwvIo82LjsqIg+IyFeXv19Tco3LNXWtU+12OTQVyAMPAH8lhPBXgf8L3AEgIjcCtwBvAW4G/r2I7BRbJTwK/Czw6Y7rHg8h/LXlr/d2XD9lnetU+Hi2+zeNx/ATpRcDsHx8fpvFW3XcCLx7+Thq7ceXj5+m13Z/hMX21ux24KEQwg3AQ8vPS/cR9q8TFG6Xm6QC+RDCp0II8eeBH2bxunpYvCzz3hDC+RDC11m8WuemEmsECCF8KYTwlVL3P7QV61T1eBrpJuBMCOFrIYQLwL0sHkdvYCGETwPfbF18Erhn+fE9wM9MuaauetZpPhXIt/pl4L8vP+57ewSNvVFE/reI/E8R+bulF9OT9sfzV5en7D6s4Z/vy7Q/Zs0C8CkR+dzy7UI0d6zxszPfAI6VXMyaNG6Xg5vs3aiGvD2CiNwJ7LL46dkiDX0bh1bPAn8phPCiiPwN4L+KyFtab+CmYZ1FW7VmFu9U+gEWUH0A+NcsDvje8P5OCOEZEfmLwAMi8uXldKq6EEIQEa2v5Ta/XU6G/Lq3RxCR9wA/CbwtvPzi/cnfHmGDt3Fo/pnzwPnlx58TkceBNwHZvvm1zTop/HYTQ9csIv8J+OPMyxmambfoCCE8s/z9eRH5OItTTVqRfy6+M62IXMvi/6NQVwjhufixsu1ycCpO14jIzcCvAz8dQmi+9+T9wC0icqWIvJHF+9N/tsQaVyUir43fwBSRH2Wxzq+VXVVnah/P5Y4eexeLbx5r6E+BG0TkjSJyBYtvXN9feE37EpEjInJ1/Bj4h+h5DLu6H7h1+fGtgNZ/fWrdLocXQij+i8U3AJ8CvrD89TuN6+4EHge+Aryj8DrfxeKc7HngOeCTy8t/DnhsufbPAz+lcZ3aHs/Wmn8P+CLwZywAuLb0mhpreyeLV309zuJ0WPE1dazxR4H/s/z1mKZ1An/A4pTmS8vt8jbg1SxeVfNV4EHgqNJ1qt0uh/7ytzXwPM+rOBWnazzP87w8OfKe53kV58h7nudVnCPveZ5XcY6853lexTnynud5FefIe57nVdz/B6S2o3mJFHBnAAAAAElFTkSuQmCC\n" }, "metadata": { "needs_background": "light" } } ] }, { "cell_type": "markdown", "source": [ "The yellow area shows the values that are greater. From calculus, we know that the maximum is found at $x^*$ such that: \n", "\n", "$$\\nabla f(x^*) = [0, ..., 0]^T$$\n", "\n", "In this example the gradient is a vector of length 2: \n", "$$\\nabla f(x) = [8-2*x_1, 16-2*x_2]^T$$\n", "\n", "We can easily find the solution analytically with a linear system of equations, one equation for each component of the gradient: \n", "\n", "$$8-2*x_1 = 0$$\n", "$$16-2*x_2 = 0$$\n", "\n", "So, the maximum is found at: \n", "\n", "$$x_1 = 4$$\n", "$$x_2 = 8$$\n", "\n", "However, in many applications, particularly in machine learning, it is computationally expensive (we would need a lot of computational resources) to find the solution of $\\nabla f(x^*) = [0, ..., 0]^T$ analytically. In those cases, gradient-descent methods are a very efficient solution to find an approximate solution. \n", "\n", "The strategy of GD methods is based on the following, it is expensive to find the value of x where the gradient is zero, but it is easy (in computational terms) to compute the value of the gradient for any value of x (e.g. $x'$). Now, if the value of the gradient at $x'$ is sufficiently small (for instance, smaller than an arbitrary error $\\epsilon$ in absolute value, $|\\nabla f(x')| \\leq [\\epsilon, ..., \\epsilon]^T$, then we can consider that it is a good estimate of the maximum! \n", "\n", "For instance, the steepest method starts at an initial $x'$, and iteratively, updates this value as: \n", "\n", "$$x'' = x' + t*\\nabla f(x')$$\n", "\n", "where t is a parameter known as the **learning rate**. The gradient is a vector that tells us the direction of **maximum change** of the function, so the algorithm takes a step in this direction at every iteration (a step of size t). When the gradient is \"reasonably close to zero\", the algorithm has found an approximation, and if not, it tries updating the value again, making x' = x'' and repeating the calculation above. Intuitively, think that you are in a mountain, and you want to get to the top, but the mountain is really high, and there are trees around you, so you do not really know how to get there. However, at every step, you can move in the direction where the slope is steepest. This is what the simple gradient descent algorithm does. Note that since it is a maximization problem (and we want to get to the top of the mountain), we update x with a positive increment in the direction of the gradient. For **minimization**, we would update with a negative increment ($x'' = x' - t*\\nabla f(x')$).\n", "\n" ], "metadata": { "id": "1PCl7lsjksUY" } }, { "cell_type": "markdown", "source": [ "#### Define the gradient\n", "Ok, to make things simple and easy to update, let us define another Python function to calculate the gradient. This function will take an array as ($x=[x_1, x_2, ..., x_3]$ and return an array with the gradient of the function. By default, it will compute $\\nabla(x) = [\\frac{\\delta f(x)}{\\delta x_1}, \\frac{\\delta f(x)}{\\delta x_2}] = [-2*x_1 + 8, -2*x + 16]$, but you can update it if you would like to test some other function." ], "metadata": { "id": "Mli34dNxddy7" } }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "XHd_WC4fGpSd" }, "outputs": [], "source": [ "def gradient_func(x):\n", " \n", " # This function returns the gradient as a Numpy array.\n", " # y will contain the gradient, we initialize it as a zero array.\n", " # since x has two components, x_1 and x_2, we initialize it as an array \n", " # with two members:\n", " y = [0, 0]\n", " # This is the gradient of the function (8-x_1)*x_1+(16-x_2)*x_2 \n", " # Here we have the first component of the gradient (-2*x_1 +8)\n", " y[0] = -2*x[0]+8\n", " # And here the second component (-2*x_2 + 16):\n", " y[1] = -2*x[1]+16\n", " return np.array(y)\n", "\n", "\n", "\n", " " ] }, { "cell_type": "markdown", "source": [ "#### Gradient descent function\n", "Ok, now, let us program another function in Python to run the Simple Gradient Descent algorithm. This function takes the following parameters: \n", "\n", "- **start:** The starting value of x'. This is where our hike to the top (or bottom) of the mountain starts. \n", "- **learn_rate:** The learning rate t, or the size of the steps that we are going to take. \n", "- **max_iter:** Maximum number of iterations, to control that we do not enter and endless loop (or an endless hike..)\n", "- **tol**: This is the tolerance, or the maximum error in the approximation of the gradient $\\epsilon$. In other words, how close we want to get to the actual top of the mountain. This parameter is optional and by default takes the value 0.01\n", "- **sense**: This is the sense or type of optimization problem. By default, the sense is \"max\" for maximization problem (to hike uphill to the top of the mountain. You can use ```sense=\"min\"``` for a minimization problem.\n", "- **gradient**: This is a function that computes the gradient, by default is the function ```gradient_func``` we have defined before. \n", "\n", "The algorithm will return: \n", "- **iterations**: An array that contains the value of x and the error at every iteration. " ], "metadata": { "id": "ELEuF6j9deYU" } }, { "cell_type": "code", "source": [ "def gradient_descent(start, learn_rate, max_iter, tol =0.01, sense=\"max\", gradient=gradient_func):\n", " iterations = [] #Let's keep track of all iterations in a dict\n", " x = start\n", " for i in range(max_iter):\n", " g = gradient(x)\n", " error = np.absolute(np.array(g))\n", " iterations.append([np.copy(x), np.copy(error)]) #Append to the iteration, a copy of the value and the error obtained\n", "\n", " tolerance = tol*np.ones(error.shape)\n", " if np.all(error <= tol): #If we are below tolerance, exit the for loop\n", " break\n", " step = learn_rate*g\n", " if sense == \"max\":\n", " x += learn_rate*g\n", " else:\n", " x -= learn_rate*g\n", " return iterations\n" ], "metadata": { "id": "thLsdv4CU8V2" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "#### Testing the gradient descent\n", "Ok, Let's test the algorithm starting at $x = [x_1, x_2] = 0$, and use $t = 0.147$ and $epsilon = 0.1$. We will then show the result iterations in a Pandas dataframe so that we can visualize the results in a table." ], "metadata": { "id": "csAm63Axde3L" } }, { "cell_type": "code", "source": [ "## These are the parameters for the Simple Gradient Descent\n", "start_point = np.array([0.0, 0.0])\n", "t = 0.25\n", "tolerance = 0.1\n", "\n", "# Let us compute the iterations\n", "iter = gradient_descent(start_point, t, max_iter=100, tol=tolerance)\n", "\n", "# Now, Let's plot the info in a dataframe\n", "pd.DataFrame(iter, columns= [\"X\", \"error\"])\n", "\n" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 331 }, "id": "tPYrpi9ySbXn", "outputId": "f30c8f91-4e3c-49fc-ea66-231d0a291d51" }, "execution_count": null, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ " X error\n", "0 [0.0, 0.0] [8.0, 16.0]\n", "1 [2.0, 4.0] [4.0, 8.0]\n", "2 [3.0, 6.0] [2.0, 4.0]\n", "3 [3.5, 7.0] [1.0, 2.0]\n", "4 [3.75, 7.5] [0.5, 1.0]\n", "5 [3.875, 7.75] [0.25, 0.5]\n", "6 [3.9375, 7.875] [0.125, 0.25]\n", "7 [3.96875, 7.9375] [0.0625, 0.125]\n", "8 [3.984375, 7.96875] [0.03125, 0.0625]" ], "text/html": [ "\n", "
\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Xerror
0[0.0, 0.0][8.0, 16.0]
1[2.0, 4.0][4.0, 8.0]
2[3.0, 6.0][2.0, 4.0]
3[3.5, 7.0][1.0, 2.0]
4[3.75, 7.5][0.5, 1.0]
5[3.875, 7.75][0.25, 0.5]
6[3.9375, 7.875][0.125, 0.25]
7[3.96875, 7.9375][0.0625, 0.125]
8[3.984375, 7.96875][0.03125, 0.0625]
\n", "
\n", " \n", " \n", " \n", "\n", " \n", "
\n", "
\n", " " ] }, "metadata": {}, "execution_count": 25 } ] }, { "cell_type": "markdown", "source": [ "Ok, let us visualize the result in a contour graph. We are going to use red arrows to represent how the different iterations converge to the maximum. Each red arrow starts at x' and stops at x'' (x' ⇒ x'')." ], "metadata": { "id": "7T3No-FNdf37" } }, { "cell_type": "code", "source": [ "x_1 = np.arange(-2, 10, 0.01)\n", "x_2 = np.arange(-2, 15, 0.01)\n", "xx, yy = np.meshgrid(x_1, x_2, sparse=True)\n", "z = my_func([xx, yy])\n", "h = plt.contourf(x_1,x_2,z,levels=10)\n", "for i in range(1,len(iter)):\n", " start_point = iter[i-1][0]\n", " end_point = iter[i][0]\n", " plt.arrow(start_point[0], start_point[1], end_point[0] - start_point[0], end_point[1] - start_point[1], \n", " color='red', width=0.1, head_width=0.4, head_length=1, length_includes_head=True)\n", "\n", "plt.show()" ], "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 265 }, "id": "LxNkbho4Tr7H", "outputId": "3390c792-990a-4a73-8382-77fb5ef99d4c" }, "execution_count": null, "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAD4CAYAAADxeG0DAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAAsTAAALEwEAmpwYAAAluklEQVR4nO3deZxbZb348c83mczWHehCF2hllVutXBFRBJFdqHKv4gKCgGBFhMsVr0Dx5Y/fD9xQVDaXWzZFELwCigsiuAIiICBrWS5QlpaWtnTvbMnk+/sjc9rTdCaTTE5yzvOc7/v14kUnSXOemZzzmadPchJRVYwxxrgrE/cAjDHG1MdCbowxjrOQG2OM4yzkxhjjOAu5McY4riWWjXaM0tYx2wx7u2KuCYOJiObs1T+1yOaKcQ/BOf15m3fVQvIS9xCqlslXd7vuFYtXqurE8stjCXnrmG3Y9WNnDXpd15QmD2aEeqdU+ZNPoQlT1sc9hNRavWxM3ENIrLZlbswMO5cNfd1jV5z18mCXxxLyci7E28K9mYU6uYZ7bNIc+vAxnOSoh3tYKephsYY86QFPc7wt1n6q9LimKfLlx3ZSwx40crigxxLyYi65EU9TvC3WJizNkU/6bH24XiZiaSVuaYi3RdvUY7D9x9e4Jz3qg0ltyH2Ot0XbNEMa4u5K1FMVch/jbdE2SeJz3JMcde9D7lO8LdrGRT7GPWlR9zLkvsTbwm18Vb5vuxz2JES96pCLyDXAXGC5qs4uu+4LwMXARFVdGe0Qq+d6wC3cJq18CXvQoGYHvZYZ+Y+AK4DrwheKyAzgUOCV6IZVPZfjbeE2ZnCuh73Zs/SqQ66qd4vIzEGu+i5wNnBbVIOqhqsBt3gbU7vwceNq1BsZ9LrWyEXkKGCJqj4mUvkNakRkHjAPoGXchBFtz8V4W7iNiZars/VGztJHHHIR6QTOo7SsMixVXQAsAGifNqOmtwp0LeAW78aYM/G1uIcQmcdWTI17CN5wcbYe9Sy9nhn5TsAsIJiNTwceEZG9VbXKt3qpzKWAW7xHxqc416KW79uiXz3Xoh5V0EccclV9ApgUfC0iLwF7RfGqFVcCbvGuLK2Rjlo1P0eL/dZcinq9Qa/l5Yc3AgcA24nIYuB8Vb16RFsdhMXbTRbrZKj0OFjk3Yn6SNfRa3nVyjHDXD+z6q2GuBBwi7cF22VDPXZpDbxrUa8m6LGd2WkBTyYLdnpY4Dcf464HPZaQJ/nzLdMUb4u2Gcxg+4XvcXdhll5p8uvle63UKi3xtnCbkSrfd3wOuwtRL5fqkPsccIu2aaS0zNpdWHqBlIbc14BbvE2cwvufb1FPetBTE3If423hNknl61JMUpddvA+5TwG3cBtX+Rj2JM3SvQ25LwG3eBsf+bQMk4SgexdyHwJu8TZp4kvU4wy6NyF3PeAWb2P8iHocQXc+5C4H3OJtzNBcj3ozg+5syF0NuMXbmNq5HPVmBN25kLsYcIu3MdFxNeqNDLozIbeAm2rtN/652LZ9z5pdY9t2GgXHWNqD7kTIXYu4BTxacYa5VrWO1cIfDVeDHlXMEx1ylwJu8R4ZlyLdCNV8/xb76rm27BLV7LyWTwi6BpgLLFfV2QOXfQv4ANAHvACcpKpr6hoRFnAfpT3Y9RjqZ2eBr8ylWXq9Qa9lRv4j4ArgutBldwHzVbUgIhcB84FzRjSSAa5E3AI+OAt281jgq+Na0EcS81o+6u1uEZlZdtmdoS/vB46ueQQDLODusWgn02CPi8XdnaCPZHYe5Rr5p4CfjeQvuhBxC7iF22Xlj12aw+5S0KuNeSQhF5EvAQXghgq3mQfMA8huMx6wgCedhdtfFnY3gl7t7LzukIvIiZSeBD1IVYf8ME5VXQAsAGibOV2THvE0BtzCnV5pDrsrQa8U87pCLiKHA2cD71XVrmr/XjZXrGezDZW2gFu8zWDC+0Vaop70oE+Ysp5Xhriulpcf3ggcAGwnIouB8ym9SqUNuEtEAO5X1VPrG2480hJwC7epVdpm60kP+mBqedXKMYNcfHWEY4mN7xG3eJsopWW2Pmfia87EPNFndjaazwG3eJtm8D3qrszOUxlyC7gx0Qv2PQt686Uu5D5G3OJtksTnWXpSl1tSE3ILuDHN5+MsPYmz81SE3LeIW8CNa3wNelJi7n3IfYm4xdv4wLdll6TE3NuQW8CNSTZfZulJWGrxMuQ+RNwCbtLCp6DHFfNMLFttIIu4MW7yYb+Pqz9ezchdj7gPO7Ix9fBhdh7HzNyLkFvAjfGL60Fv9rq58yF3OeIWcGMq8yHozYi502vkFnFj0sHl46UZnXJ2Ru5qxF3eIY2Jk8uz80bPzJ2ckVvEjUkvV4+jRnbLuZBbxI0xrh5PjeqXU0srLkbc1R3OmKRzdamlEcsstXzU2zWUPmR5uarOHrhsG+BnwEzgJeCjqro60hEOsIibWhzc+XzTt/mHrp2bvk1TOs7SHvNaZuQ/Aq4Argtddi7wR1X9hoicO/D1OZGNzmEW8caKI9TDGW5MFvrGcTHmUarlMzvvFpGZZRcfRekDmQF+DPyFBoTctdm4RTxaSYz2SAz2fVjco+NazKOclde7Rj5ZVZcO/HkZMHmoG4rIPGAeQG7i2Ko3YBFPH1/CXY3y79XCXp+0xjyyJztVVUVEK1y/AFgA0LnL1CFvF2YRT480xbuS8M/Boj4yaYx5vSF/XUS2V9WlIrI9sLzO+3OWRbw2Fu7h2Wx95FyLeb3qfR35r4ATBv58AnBbnfe3iUuzcYt49Q7ufN4iPkL2s6uNS8dlvb2r5eWHN1J6YnM7EVkMnA98A/gfETkZeBn4aF2jGWAR94vFJ1q2/FI9l2bm9Syx1PKqlWOGuOqgEW3ZAxbxyizgjRf8jC3oQ3Mp5iOVuFP0XZmNW8SHZksAzWc/88pcOV5H2r9Ehdwi7jaLSfzsMRiaz8dtokJu3GXxSBZ7PNw1kgltYkJus3E32Qwwueyx2Zqvx29iQu4CX3eCkbJIuMEepy25cBzXOrF16m1sTTJYGNxjr27xWyJm5C4sq7jwW7wZLOJus8evxIXjuZYuJiLkxg0WAT/Y4+gfC3kVXPjt3Wh28PvFHk+/juvYQ+7Cskra2UHvJ3tck6/aPsYecmOMMfWxkA/Dp39+jYTN2vyW9sfXl+PbQm6GlPaDPC3scXZfrCG39XFjjKmsmk7ajNwMymZpxrjDQl6BL+tnxgwnzb+4fTjOLeTGGOO4SEIuIp8XkadE5EkRuVFE2qO4X2OMMcOrO+QiMg34D2AvVZ0NZIGP13u/xhhjqhPV0koL0CEiLUAnYC9HMe5QJft6P5k1RVCNezTG1Kzut7FV1SUicjHwCtAN3Kmqd5bfTkTmAfMAchPH1rtZY6JRKDLpU2vo/HMfAJqBV56ZjHZIzAMzpnpRLK1MAI4CZgFTgVEiclz57VR1garupap7tYwbVe9mjalfV5Edd16+KeIAxfGC9Nqs3LgliqWVg4FFqrpCVfPArcC7I7hfYxqm7e4eZu62HOnf8vKlv9iW4nh7MZdxSxSfEPQKsI+IdFJaWjkIeCiC+zUmctJVZMq/v0Hbwv6trnvloe0oTrYPzTLuqXvqoaoPADcDjwBPDNzngnrv15hIqTLu8vXssNvyTREPL6As+eUEi3hK3bNm17iHULdI/g2pquer6u6qOltVj1fV3ijuN24+PMAj5dNnO7Y+2MuMPZYz4ZsbETYHPHg6c+NhreTf3hbT6JLBp8c7jWwKYrwlq/qZ/InVtD1Z2BRtBbQFpDDwdRZWXj4hriEaE4lYn9V5bMXUODdvhuHsLK2oTPi/a9lhzootIl6kNAvPBBEH3rhwdOpfaujs45wS1XTSZuTGKx1/6GbiqWuR3s1LJ7A54hr6f/+kDBuOs5fCGvfZ66yGkeZ1cnBntpZ5rZ+p+61g0klryfRujnWwHh7s6OG4v379BBCbjaeZL8e3hdwMK+kHe3ZxgRnvWkHrS/1brIULbPV18Oeug1rJvznX5JEmS9IfV1O92EPuwjq5L7+165HYgz6vTDtwZWntZEA42oEtvs7Ayu+Nb/jQkiyxj2cTuXBcV9vH2ENu3JG0g7/t/j6m7b8C8lvOtoP/6yCrJgqs+vJodFR6d/2kPY6mfundm2vkwm/vZkhSBMZcs5GWxcXNLyUEkIH18Xa2OOMnWC/f8LF21p+c3ic4k/T4xcm34zkRIXdhecVsFncMpKvIhAvX0fnn3s3hDq7UgaWVni1n6YUZGZZfM443Lh6f2ic4437cTG1q6WIiQu4K336L1yOWKKgy6rZupr9zBWOu6yLTAzIQbjID4c6UTvIRSksrmgNaYPnVE+g+pKP5Y04Ii/hmPh7HiXkd+WMrpjJnon0ehUuCODTrg3tzz/cz8fS1aA4kX7ps0xObwZOdxc2zEx0tLL5vO7Q9g7bbLNy4o9ZVCpuR18jH3+b1alYs8jtnWXrLNvTt2oIO7LnhPIdfrVLsFFadP4bi+KxF3Gzi6/GbqJC7slbu685Qjz907dzYcPQq4y7byOTjVtH6bAEpbnm1ZqA4TtBWKHZAYUaWDR9J51JKwx8LR7ly3I6kg4lZWjF+aMRyS8cfe9j2nHVk1hXJdA9+G+0Qlvx1IsWxQuvCAoUdspBJ10zc4p1eiQu5K2vl96zZlf3GPxf3MBIriqC3LCqw7TlraXs0P2TAobSMsvrs0RS3Lf0Ds29Ous7YtIAPz+fZOCQw5C6xmA9vJEGXriLjv72BMdd1IX1stYxSrn9ShvUndNYzTCdZwKvjSsTrEUnIRWQ8cBUwm9JzTp9S1b+P9P5cmZWDxbxa4ehUinp2WT9TD1lJZr1u9Xmagyl2wMrvjINsOpZRLN61cSni9TxHGNWM/FLgDlU9WkRagbqnRxZzf1WKenGssOHoDjru6SX3Yj+aEzJdg3+qveag+31t9L6jtaHjjZvFe2TSEnGIIOQiMg7YHzgRQFX7gL567xcs5mlQHnXtzLD6/LGsVmXyR1fR9s/SC8aLrSD9oK2AlOKuOWHVBWNjGnljWbzrk6aIQzQz8lnACuBaEZkDPAycqaobwzcSkXnAPIDcRD8PPot5fcLxym0ocMyylUi+NPPue2uO138ygeyKIm0P52m/t5fu97XRPzkb44ijY+GOjksRj4qoDv7P1qrvQGQv4H5gX1V9QEQuBdap6peH+judu0zVXS85ueptuDIrD1jM66DKzr9czru+9iKt6/p59NPTePaY7dk4qZWDxr0Y9+giY+FuDNciXuts/LG5X3lYVfcqvzyKGfliYLGqPjDw9c3AuRHc7yYuLbGAzcxHatunNrD//OcY+0oPue4i3dvkePT0HehvL826h4pfs94iYCQs2M3je8QrqTvkqrpMRF4Vkd1U9VngIGBh/UPbksXcX22r8uzzjUXMumMl2d4iAuQ7Mtx7wU6bIl7JcLFsZOgt1MmQ5ohDdK9aOQO4YeAVKy8CJ0V0v1twMeZgSy1DkYLy5p8u5R3ffQkpKC19pWW+YgZW7jGalw/eNpLtWGz95VrAoTFvRRJJyFX1UWCrdZtGcC3mYLPzwUz5x1r2n/+/dKzsI9e95Rk/xVyGe766S2rfN9xUxyK+WaLeNKtarry5VpiLO10jdC7r5eDTFnL4KU8x9tWerSJeaMvw9DFTWDcrnW94Zarj4vHUyG45e4q+qzNzSOdSS6avyFuvXMycBYvJFIpkC4PfrtCR4eEzd2zu4IwzXAw4NH7y6eSMPODizBzc3RlHasaf3+BjB/6DOQsWk+sZOuL5jgx/O38nCp1+vDbcRMvV46YZnXJ2Rh5wcWYO6Zidj32pm/d8+XkmPrF+qyWUckWB1bt0suj92zVpdMYVrgYcmjfZdD7k4G7Mwd+gd6zo4+gjHkH6lWqesiy2Zrj767vaE5xmE5cDDs1dMXB6aSXM1WWWgOs7bbmebXL86bu7sfATU1g/rQ2t0OdCm/DshyezZuf0vRWtGZzrx0Oze+TFjDzg8swc/Jqda1Z46bDtWP62Mcz462qKLUI2r+TbM3RPzNGxcvOnJxdbhYe+YE9wGvcDDvFMKr0KObgfc/An6GNf6mbusY/TtiZPtr/0ZOaL79+Oe7+yCyowblE3kx9Zx6rdOsmP9m5XNDXwIeAQ38qAl0dP8MO0oMdn26c2cMQJT5Db0E9GId+e4alPTuWhz++4aR187U6drN3JllPSzAIeDS9DHvBhdg7uBX37+9dw6KkLN71SpdCe4aHP78hTJ06LeWQmKXwJOMQfcfA85OBPzMGNoM/8/UoOOPs5Wno2R/zur+zMix+YFPPITBL4FHBIRsQhBSEHf5ZaAuGDIUlR3/3GpezzjUWbIp5vz/CHK3ZnyX7bxDwyEyff4g3JCXggFSEP+DQ7DyRilq7K277/Km9bsJiWniIK5Edl+d21s1kxZ0x84zKx8jHgkLyIQ8pCDv7NzgOxzdKLyrsvfIFdbl1OS0+RYgb6xrbwmxveaq8LTyFf4w3JDHggdSEP+Bp0aN4sXfJFDjzrWabfs5pcT5H+Fuie2Mavf/oWNk5tb+i2TbJYwOOV2pAHfFxuCTRylp7t7uewzyxk4mPryfUUKbQK62e085vr30rvNrlIt2WSyed4B1yIOFjIAb9n54Eoo966tsCRn3yCcYu6aOktna25avdR3HH1v9iJPZ5LQ7zBnYAHIjvqRCQLPAQsUdW5Ud1vM6Uh6LD1wVhL2Dtf72XusY8z6vW+Tafcv7bPOP54+Zsptnrz1j1mQFrCHXAt4IEop09nAk8DY4e7YX8+2Qd8WoIeqHa2Pvalbj5w7OO0DnbKfdbetdAXaYs3uBHw1cuGfgVYJCEXkenAkcBXgbNqGdSEKeujGEJD+Lx+PpRKs/XDT36S9lV5ZIhT7o2b0hjusKRHvFLAA1HNyC8BzgaG3KKIzAPmAWS3Gb/p8tXLxiQ+5pCe2Xm5e9bsCqrseffLZNYp+Y4Mq3YbxQtzJ/L0cck+AMzg0h7uQNIDDtVFHCIIuYjMBZar6sMicsBQt1PVBcACgLaZ0zV8nSuzc0hf0Ke8vJZPffUeZj77Bq29/Xz/gvfy4KE7la5cU/pfks4uNVuyaG/Np4AHopiR7wt8UESOANqBsSJyvaoeV+sdJX12DlvuBD5HvX1DHx/+74c54LbnyPb1I8CiN2/Hg4e8aavbDhYLi3vzWbSH5kK8A7VGHCIIuarOB+YDDMzI/2skEQ+4MDsPeDlLV2Xf25/nE999gJbeflr7+gHoa8ty1Zf3q3o9fKioWODrZ8Gunu8BDyT2Rb8W9Obb8ZmVnHLhPUxasp727s0fdd/XmuXuubuw5E0T6t5GpQhZ5DezWNcnLQEPRBpyVf0L8Jco79OF5ZaAq0EfvaaHYy55gL3/9BItvf1bfZBrvjXLz0/bq+HjqCZePsTeIt04LgUcook4JHhGHubS7BzcWUfPFIoceMvTfOQHD5MtFMnli1vdpqe9hRvOeic9o1tjGOHWooxgLb8ULL7J5Vq8IbqAB5wIecC1oENyZ+m7/XMZJ194D+Pe6Ka9pzDobYrA6zPG8rcjdm7u4JrE4uw2C/hmToU84HLQId6oT3h9I8df/HdmP7CEtt7+ircttGW56v9U/wSnMY3mYryhcQEPOBnygItBh3iinikUmfvjx5h73eNk80Va+rXi7fO5DPcd9iZe2XXbpozPmKG4Gm9ofMADToc84GrQoXlRF+DQmxaS6VfyrVlaugdfTgnkW7P8z+l7N2w8xlTicryheQEPeBHygMtBh8ZGvb8lw+l3HsvE19Yz98ePs9+v/5dssTQr72lvIddXIDvwXGdPRws3nfEONo5ri3QMxlTieryh+QEPeBXygOtBhwZFXYQdnn2Dd93xwqaI97Zl+eWn96RzXS9veWAJ019YzfJpY7j7qN2i2aYxFfgQb4gv4AEvQx7wIeiw9c4+0rAfcOszHHvJA5ue5Oxpb+Hyiw7kyX2mA3DLaXuRKZSm5ZqxJzhN9HwJdyDugAe8DnnAl6AHap6tq/LBqx9l7nWP09bbTxHoHZXjm5cdxouzJ21x02JLst8r3rjHt3hDcgIeSEXIA74FHYafrUtROe7iv7Pfb5+nrbef/oywcWwrX/vhkSydNb6JIzVp4WO4A0kLeCBVIQ+EHwyfog5bHkQthX6+f9mNvPW+V2nr6afQIqzdtpOvXHkkqyaPjnGUxic+hxuSG++wVIY8zMdZOkB7T57L/t9NvOW5JbT39tOTy7J4+wl898pD2TC+Pe7hGYf5Hu6ACwEPpD7kAZ9m6WM2dHPV/J+w4+JVtOcL9LS28MxOU/jsBcfSnW+FFVvePmlvH2CSIy3RDrgU77BYQi55oW1Zjt4p+Tg2PyyXZ+kT31jPtWf/mElvrKe10E93W44H5szkv+YfTSGXHfTvDHawWtzTJ23RDrgQ77ZluYrXxzojDwaX9KCDG1HfYckqrjnnx4xf10VLUelqy/H7/ffgwtOPpJit7dUoQx3UFnj3pTXY5XwIeCARSytJDzokP+q7P7+UBV+6ntFdvWQUuttauOGovfne8QdE+qZXFnh3WLC35kK8ofqAB6L48OUZwHXAZECBBap66Ujuy4WgQ/KivtfjL3HZBT+js6f0c+tpbeGyTx7IjUc1771ShouGhT56FurquBJvqD3ggShm5AXgC6r6iIiMAR4WkbtUdeFI7zD8zVjUK3vffU/ztW/fRkdv6U2welpbOP/MD/D79/5L08dSSTXRsdhvZpGuTxriHRbFhy8vBZYO/Hm9iDwNTANGHPIwV2bp0Pyof/h3j/DFK++kva8U8a62HF8472j+/vadGr7tRhhpvJL8C8CC3DwuxRuiCXgg0jVyEZkJ7Ak8EOX9gltBh613qkjDrsq8m+7hpJ/fR3tfgSLQ1dHKqV/5BE/uNi267TjCYplOroU7EGXAA5GFXERGA7cA/6mq6wa5fh4wD6Bl3Mg/jd2lZZewqGbrUlTO/eEdfPCPj9PRV6A/I6wb3c6nLjqBRTO2i2KoxiSWxXtwkYRcRHKUIn6Dqt462G1UdQGwAKB92ozKH09TJddm6YGRztZbCv18/Vu/YN+HXqCjN08+m2HlNqM58Zsn8PrEcY0YqjGxcjXcgUYHPBDFq1YEuBp4WlW/U/+QaufqLD1QTdjDp9x39BY2nXJ/ytc/yZpxnc0aqjEN5Xq4oXnxDotiRr4vcDzwhIg8OnDZeap6ewT3XTNXZ+lh5TvzDqOXD33KfUdrTKM0pn4+hDsQR8ADUbxq5V5KHwmZKK7P0gOT1qzjhnOvZfLqtbT199PVmuPBt83ki/M/TD6XiPO5jKmaT+GGeOMdlooSuBr1ma+v5OaLfsD4DV3kikW6WnP8au85zP/khym+seUp90k4McmYMN+iHUhKvMNSEfIwV6I+++Ul/PTiBYzp7iEDdLXmuPrg93Dxvx826Cn3DX25ozFV8DXckMx4h6Uu5GFJjfq7nnmBqy//EaN6+wDozuX45ocO59qD31P1fQx1UFngTb18DnZY0uMdluqQhyUl6oc9/ASXXv0zOvpKY+jO5Tj7hA/zq332jOT+LfCmWmkJdphL8Q6LJeSZPHQuK/25a0ocI6gsrqgf89f7Of+m39CRL22zqzXHvNOO557ZuzV82xb49EpjsMOSHu+glZXEPiNPctBh6we5IWFX5Yzf/JHP/e4vdOTzFIGN7W0cd9YpPPqmHaLfXg0qHeQWeXekPdZhSQ93oJqAB2IPeSA86KRGHaKfrUuxyAU/vY2j73uYjr48BRHWjergI2efyvNTJ9d9/41UTRws9o1nkR6ej/EOS0zIw1yMOtQe9pZCP5ddeSPve+IZOvvy9GUzrBg3hqPP+SyvbTvy96NJkloiY9HfzOJcH1fCDSOPd1giQx6W9KWXsFrC3t7bx7WXXcvbFr1KZ1+enpYWXp60LR/74mdYPWZUo4eaSFHEKwm/DCzCzedSuANRBDyQ+JAHXJmlhw0V9rEbu7jp4gW8adkKOvIFunMtPLXDNI7//Ml0tbfFMVRvWETTwcVwQ7TxDnMm5GEuRh1KO9+kdWv56ZWXM2XdWloHTrn/2+47c9pnj6PPTrk3ZlCuhhsaF+8w58vhUtR3XLmCG6+6nPFdXbQUi3TlWvnt7Lfx5X/7KPJGBhJ0UpIxcXE52oFmxDvM+ZCHJTnqb35tMT+55vuM7imdct+dy/Gjd+/HJQcfsemU+8F24CSdcWpMI/gQbmh+vMO8CnlYkqK+94vP89/XX8Wovs2n3H/7kCO57t37D/t3Le7GJ75EOxBnvMO8DXlY+Q+7mWE/5KnHufjmGzadrdmdy3Hev32U3855+4jvc6iDwQJvksK3YAeSEu5yqQh5uWbN1j/24H2cd/ttdBQGTrnP5fjcsSfxt112b8j2LPCm2XwNdlhS4x2WypCHNWS2rsppf7mLz9z9RzoKA6fct7Vx0omn8viMHSPYQG0s8KZeaQh2wIVwl4vqw5cPBy4FssBVqvqNSrfP5GH0a/1smJqNYvORqne2LsUiX/7tL/jQIw/SkR845b6jg0+ccgYvTErWKfeVDk6LfPqkKdblkh7v0a/1V7w+ig9fzgLfAw4BFgP/EJFfqerCWgaX9KjD8GFv6e/n2z+/nvc+u5DOfJ6+TIaVY8ZyzKfPYOl4t065H+6gttC7J82hLpf0cMPw8Q6LYka+N/C8qr4IICI3AUcBw4Y8LOlRh+HDftEtP+XQpx4nq0pPtoVXt9mW4075HKtHjW7eIJuk2ihY8BvPAj08F8INtcU7LIqQTwNeDX29GHhn+Y1EZB4wD6CtY3zFO3Qh6rD1zvH7GW+ns7ePf311Ec9N2p7PHH8KXW3pPuV+JJFJc/wtyvVzJdqBkcY7rGlPdqrqAmABwOgJM7Tav+dK1AHunbUH987aY/MFq4GEnZjkAouZqYVr4YZo4h0WRciXADNCX08fuCxyLkU9MNhOFvcJSsa4ysVoB6KOd1gUIf8HsIuIzKIU8I8Dx0ZwvxWV/1BcCTtY3I2phsvRhsaGu1zdIVfVgoicDvye0ssPr1HVp+oeWY1cnK2HWdxNmrke7UAz4x0WyRq5qt4O3B7FfUXB5dl62FA7twXeuMqXYAfiCne5VJzZ6UvYAxZ4k3S+BTuQlHCXS0XIy/kW9oAF3jSbr8EOJDXc5VIZ8nK+hj0w3MFmoTdD8T3U5VwJd7lYQp7t62fUKxsB2LhD8j5o2Pewl7PQp1faQl3OhXAHrawk9hl5eJBJjDqkL+zlqj3YLfjJkfZAD8WFcEN18Q6LPeRh5YN3JeyQvrgPptZ4WPirZ2GunSvRhtrDXS5RIS/nwmw9YHGvXdRxStIvBgtvc7kU7UC98Q5LdMjDXJmth1ncm8vimQ4uRhuiDXc5Z0JezqXZepjF3ZjquRptaGy4yzkb8jAXZ+thQ+2sFniTFi4HO6yZ8Q7zIuTlXA97wAJvfONLsANxhbuclyEv50vYA5UOBou8iZtvsQ5LSrjLpSLk5QZ7MFyPe8Aib5rB51gHkhrtwcQT8t7kfZSXb7P2wVRz8FnsTRoiPZikh1sWDf15PbHNyMsHpbOmxTSSwfk8a6/EYu+3tEa6XNKjDZXDXS4xSyvhQSct6oG0xr1crTGw8DeOhXl4LkQ7UEu8wxIT8rCkz9bDLO7Diyo2Pv1CsAA3hkvRhpGHu1xdIReRbwEfAPqAF4CTVHVNBOPacjsOhR0s7o1i8TMB14IdiCrc5eqdkd8FzB/43M6LgPnAOfUPqzLXwg5D73gWeGMqczXa0Lhwl6sr5Kp6Z+jL+4Gj6xvOyLgY9kClndQib9LC5ViHNSvcW21XVaO5I5FfAz9T1euHuH4eMG/gy9nAk5FsOJm2A1bGPYgG8vn78/l7A/v+XLejqk4sv3DYkIvIH4DB3iD0S6p628BtvgTsBXxIq/jNICIPqepeVQ3bQfb9ucvn7w3s+/PVsEsrqnpwpetF5ERgLnBQNRE3xhgTrXpftXI4cDbwXlXtimZIxhhjapGp8+9fAYwB7hKRR0Xkh1X+vQV1bjfp7Ptzl8/fG9j356XInuw0xhgTj3pn5MYYY2JmITfGGMfFFnIR+ZaIPCMij4vIL0RkfFxjiYqIHC4iz4rI8yJybtzjiZKIzBCRP4vIQhF5SkTOjHtMjSAiWRH5p4j8Ju6xRE1ExovIzQPH3dMi8q64xxQlEfn8wL75pIjcKCLtcY+pWeKckd8FzFbVtwLPUTq931kikgW+B7wf2AM4RkT2iHdUkSoAX1DVPYB9gM959v0FzgSejnsQDXIpcIeq7g7MwaPvU0SmAf8B7KWqs4Es8PF4R9U8sYVcVe9U1cLAl/cD0+MaS0T2Bp5X1RdVtQ+4CTgq5jFFRlWXquojA39eTykC7rwXQhVEZDpwJHBV3GOJmoiMA/YHrgZQ1b5GvMFdzFqADhFpATqB12IeT9MkZY38U8Dv4h5EnaYBr4a+XoxnoQuIyExgT+CBmIcStUsonRdRjHkcjTALWAFcO7B0dJWIePNmPqq6BLgYeAVYCqwtey8orzU05CLyh4H1qvL/jgrd5kuU/tl+QyPHYqIhIqOBW4D/VNV1cY8nKiIyF1iuqg/HPZYGaQH+FfiBqu4JbAS8eR5HRCZQ+hfwLGAqMEpEjot3VM3T0A+WSNnp/UuAGaGvpw9c5g0RyVGK+A2qemvc44nYvsAHReQIoB0YKyLXq6ovMVgMLFbV4F9RN+NRyIGDgUWqugJARG4F3g0M+iZ+vonzVSvB6f0f9OT0/n8Au4jILBFppfREy69iHlNkREQora8+rarfiXs8UVPV+ao6XVVnUnrs/uRRxFHVZcCrIrLbwEUHAQtjHFLUXgH2EZHOgX31IDx6Mnc4cX7U2xVAG6XT+wHuV9VTYxxPXQY+XON04PeUnjG/RlWfinlYUdoXOB54QkQeHbjsPFW9Pb4hmRqdAdwwMNF4ETgp5vFERlUfEJGbgUcoLdX+kxSdrm+n6BtjjOOS8qoVY4wxI2QhN8YYx1nIjTHGcRZyY4xxnIXcGGMcZyE3xhjHWciNMcZx/x8kQWb8yADsMwAAAABJRU5ErkJggg==\n" }, "metadata": { "needs_background": "light" } } ] }, { "cell_type": "markdown", "source": [ "# Questions\n", "\n", "1. Repeat the experimentation with lower tolerances values and note how the number of iterations increases. For instance, try to modify the script to achieve a tolerance of 0.01. How many iterations did the algorithm need, and what is the difference in the estimated x with respect to the previous experiment. What if you decrease it to 0.001?\n", "2. What happens with the distances between iterations as we get closer to the maximum? Can you reason why this happens?\n", "3. Let us experiment now with the learning rate t. Let us set the tolerance back to 0.1 and test the script above with a learning rate of 0.25. Is convergence faster (in less iterations)? Try it now with a value of 1. Did the algorithm find an optimal solution? What about 0.5? What can we say about the sensitivity of the algorithm to changes in the learning rate?\n", "4. We know where the maximum solution is. Can we use the second partial derivative test generalization to know if it is a local maximum or minimum?\n", "5. Can you repeat the experiment for another function, for instance, minimize $z = f(x) = 2*x_1^2 + x_2^2 - 10*(x_1 + x_2)$?\n", "\n", "\n" ], "metadata": { "id": "cZ-5xhr-MU1e" } } ] }